import random


class RandomizedCollection(object):

    def __init__(self):
        self.stack = []
        self.d = {}
        self.index = 0

    def insert(self, val):
        """
        :type val: int
        :rtype: bool
        """
        self.stack.append(val)
        if val in self.d:
            self.d[val].add(self.index)
            self.index += 1
            return False
        else:
            self.d[val] = {self.index}
            self.index += 1
            return True

    def remove(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val in self.d:
            index = self.d[val].pop()
            self.index -= 1
            if not self.d[val]:
                self.d.pop(val)
            self.stack[index], self.stack[self.index] = self.stack[self.index], self.stack[index]
            self.stack.pop()
            if self.index != index:
                self.d[self.stack[index]].remove(self.index)
                self.d[self.stack[index]].add(index)
            return True
        else:
            return False

    def getRandom(self):
        """
        :rtype: int
        """
        return random.choice(self.stack)


obj = RandomizedCollection()
obj.insert(1)
obj.insert(1)
obj.insert(2)
print(obj.getRandom())
obj.remove(1)